package top.humbleyuan.bfs;

import top.humbleyuan.datastructure.tree.TreeNode;

/**
 * @Author HumbleYuan
 * @Date 2020/5/19 20:06
 * @Des 将树原地转换成链表
 */
public class LeetCode_114 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.formTree();

        flatten(root);

        System.out.println("asa");
    }

    public static void flatten(TreeNode root) {
        if(root == null) {
            return;
        }

        if(root.left == null) {
            flatten(root.right);
        } else {
            if(root.right == null) {
                root.right = root.left;
            } else {
                // 将temp接到right的最右子树
                transfer(root.left, root.right);

                root.right = root.left;
            }

            flatten(root.right);

            // ** 注意要将左子树置为空
            root.left = null;
        }
    }

    public static void transfer(TreeNode root, TreeNode temp) {

        while(root.right != null) {
            root = root.right;
        }

        root.right = temp;
    }
}
